package 蓝桥._14届.互质数的个数;

import java.util.Scanner;

public class Main2 {

    static final int mod = 998244353;

    // 唯一分解定理：任何一个大于 1 的自然数 n，都可以唯一分解成有限个素数的乘积

    // 欧拉函数(n):  <=n的且与n互质的正整数的个数
    // 互质条件：两个或两个以上的整数的最大公约(因)数是1
    static long phi(long x){
        long res = x;
        for(int i=2;i<=x/i;i++){
            if (x % i == 0) {   // x的素因数，若当前x能被i整除，则i必是素数，
                // 因为如果 i 是合数，那么它必然可以分解成比它小的质数的乘积(唯一分解定理)，
                // 而这些比它小的质数在之前的遍历中已经被处理过，并且从 x 中除掉了，
                System.out.println(i);
                res = res/i* (i-1);
                while (x%i==0) x/=i;   // 将这个素因数的所有幂次除完
            }
        }
        if(x>1) res = res/x *(x-1);
        return res;
    }
    // 复制的
    //由如上算法可知,n的欧拉函数只与其质因数的组成有关,与每个质因数的个数无关
//对于不同的数字,只要它们的质因数组成相同,计算过程中就会除以相同的pi乘以相同的(pi-1)
//故若m和n的质因数组成相同,m是n的k倍,则Euler(m)也是Euler(n)的k倍
//而a^b是a的a^(b-1)倍,则由此推出Euler(a^b)=Euler(a)*(a^(b-1)),此即为最终答案

    // 快速幂
    static long quick_pow(long base, long pow, int mod){
        long t = base, result=1;
        while (pow>0){
            if(pow%2==1)
                result = (result*t)%mod;
            t = (t*t)%mod;
            pow = pow>>1;
        }
        return result%mod;
    }

    public static void main(String[] args) {

        System.out.println(phi(234354652213321L));

        Scanner scan = new Scanner(System.in);
        long a = scan.nextLong(), b = scan.nextLong();
        long euler_a = phi(a);
        long ans = euler_a*quick_pow(a,b-1,mod)%mod;
        System.out.println(ans);
        scan.close();

    }
}
